/**
 * https://leetcode.cn/submissions/detail/562694038/
 * 377. 组合总和 Ⅳ
 * Medium 黄伟杰 2024.9.9
 * 线性DP
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int dfs(int i, vector<int> &nums, vector<int> &memo)
    {
        if (i == 0)
            return 0;
        int &res = memo[i];
        if (res != -1)
            return res;
        res = 0;
        for (int x : nums)
        {
            if (x <= i)
                res += dfs(i - x, nums, memo);
        }
        return res;
    }

public:
    int combinationSum4(vector<int> &nums, int target)
    {
        vector<int> memo(target + 1, -1);
        return dfs(target, nums, memo);
    }
};